#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int T = 5e5+10;
const int SQRTT = 800;
int ql[N],qr[N],qk[N];
string sl[N];
vector<int> que[N];
int idx[N];
int n,m;
bool cmp(int x,int y){
    return 1ll*sl[x].size()*que[x].size() < 1ll*sl[y].size()*que[y].size();
}
int bestlmt(int tot){
    sort(idx + 1,idx + 1 + n,cmp);
    long double cma = 1.0l*tot*n;
    int cp = 0;
    long double dt = cma;
    for(int i = 1;i <= n;i++){
        dt -= tot;
        dt += 1ll*sl[idx[i]].size()*que[idx[i]].size()*0.5;
        if(dt < cma){
            cma = dt;
            cp = i;
        }        
    }
    return cp;
}

int dfn[T],dft;
int siz[T];
int son[T];
int top[T];
int fath[T];
int dep[T];
vector<int> bian[T];
void dfs(int x,int fa){
    dfn[x] = ++dft;
    siz[x] = 1;
    fath[x] = fa;
    dep[x] = dep[fa] + 1;
    for(int v : bian[x]){
        dfs(v,x);
        siz[x] += siz[v];
        if(siz[v] > siz[son[x]]){
            son[x] = v;
        }
    }
}
void dfs1(int x,int tf){
    top[x] = tf;
    if(!son[x]){
        return;
    }
    dfs1(son[x],tf);
    for(int v : bian[x]){
        if(v == son[x]){
            continue;
        }
        dfs1(v,v);
    }
}
int sum[T];
int ep[N];
struct segment_tree{
    int ma[N<<1];
    int ls[N<<1];
    int rs[N<<1];
    int pcnt;
    inline void push_up(int now){
        ma[now] = max(ma[rs[now]],ma[ls[now]]);
    }
    void build(int &now,int l,int r){
        now = ++pcnt;
        if(l == r){
            ma[now] = sum[dfn[ep[l]] + siz[ep[l]] - 1] - sum[dfn[ep[l]] - 1];
            return;
        }
        int mid = (l + r)/2;
        build(ls[now],l,mid);
        build(rs[now],mid+1,r);
        push_up(now);
    }
    int query(int now,int l,int r,int x,int y){
        if(x <= l && r <= y){
            return ma[now];
        }
        int mid = (l + r)/2;
        int res = 0;
        if(x <= mid){
            res = max(res,query(ls[now],l,mid,x,y));
        }
        if(mid < y){
            res = max(res,query(rs[now],mid+1,r,x,y));
        }
        return res;
    }
} sg;
struct ACAM{
    int to[T][26];
    int fail[T];
    int rot;
    int pcnt;
    int gen(){
        int now = ++pcnt;
        memset(to[now],0,sizeof(to[now]));
        fail[now] = 0;
        return now;
    }
    void init(){
        rot = gen();
    }
    int insert(string s){
        int now = rot;
        for(char c : s){
            c -= 'a';
            if(!to[now][c]){
                to[now][c] = gen();
            }
            now = to[now][c];
        }
        return now;
    }
    void build(){
        queue<int> que;
        for(int i = 0;i < 26;i++){
            if(to[rot][i]){
                que.push(to[rot][i]);
                fail[to[rot][i]] = rot;
            }else{
                to[rot][i] = rot;
            }
        }
        while(que.size()){
            int now = que.front();
            que.pop();
            bian[fail[now]].push_back(now);
            for(int i = 0;i < 26;i++){
                if(to[now][i]){
                    que.push(to[now][i]);
                    fail[to[now][i]] = to[fail[now]][i];
                }else{
                    to[now][i] = to[fail[now]][i];
                }
            }
        }
        dfs(rot,0);
        dfs1(rot,rot);
    }
} acam;
int ans[N];
vector<pair<int,int>> ps[N];
int lca(int u,int v){
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]]){
            swap(u,v);
        }
        u = fath[top[u]];
    }
    if(dep[u] < dep[v]){
        swap(u,v);
    }
    return v;
}
vector<int> bian1[T];
int cnt[T];
void dfs2(int x){
    for(int v : bian1[x]){
        dfs2(v);
        cnt[x]+=cnt[v];
    }
}
vector<int> que1[N];
struct SQB1{
    int tot,block;
    int bl[T];
    int val[T];
    int mtag[SQRTT];
    int len;
    inline int lp(int b){
        return (b - 1)*block + 1;
    }
    inline int rp(int b){
        return min(b*block,len);
    }
    void init(int n){
        len = n;
        block = sqrt(n);
        tot = len/ block + (len % block != 0);
        for(int i = 1;i <= tot;i++){
            int lb = lp(i),rb =rp(i);
            for(int j = lb;j <= rb;j++){
                bl[j] = i;
            } 
        }
    }
    void update(int l,int r,int v){
        if(bl[l] == bl[r]){
            for(int i = l;i <= r;i++){
                val[i] = v;
            }
            return;
        }
        int lb = bl[l];
        if(l > lp(bl[l])){
            for(int i = l;i <= rp(bl[l]);i++){
                val[i] = v;
            }
            lb++;
        }
        int rb = bl[r];
        if(rp(bl[r]) > r){
            for(int i = lp(bl[r]);i <= r;i++){
                val[i] = v;
            }
            rb--;
        }
        for(int i = lb;i <= rb;i++){
            mtag[i] = v;
        }
    }
    int query(int p){
        return max(mtag[bl[p]],val[p]);
    }
}bo;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    int tot = 0;
    acam.init();
    for(int i = 1;i<=n;i++){
        cin>>sl[i];
        ep[i] = acam.insert(sl[i]);
        tot += sl[i].size();
        idx[i] = i;
    }
    acam.build();
    for(int i = 1;i<=m;i++){
        cin>>ql[i]>>qr[i]>>qk[i];
        que[qk[i]].push_back(i);
    }
    int p = bestlmt(tot);
    //assert(p == n);
    for(int i = p + 1;i <= n;i++){
        int cur = acam.rot;
        for(char c : sl[idx[i]]){
            cur = acam.to[cur][c - 'a'];
            sum[dfn[cur]]++;
        }
        for(int j = 1;j <= dft;j++){
            sum[j] += sum[j - 1];
        }
        sg.pcnt = 0;
        int rt = 0;
        sg.build(rt,1,n);
        for(int p : que[idx[i]]){
            ans[p] = sg.query(rt,1,n,ql[p],qr[p]);
        }
        for(int j = 1;j<=dft;j++){
            sum[j] = 0;
        }
    }

    for(int pp = 1;pp<=p;pp++){
        int i = idx[pp];
        int cur = acam.rot;
        vector<int> nds;
        for(char c : sl[i]){
            cur = acam.to[cur][c - 'a'];
            sum[dfn[cur]]++;
            cnt[cur]++;
            nds.push_back(cur);
        }
        sort(nds.begin(),nds.end(),[](int x,int y){
            return dfn[x] < dfn[y];
        });
        for(int j = 1;j < sl[i].size();j++){
            nds.push_back(lca(nds[j - 1],nds[j]));
        }
        sort(nds.begin(),nds.end(),[](int x,int y){
            return dfn[x] < dfn[y];
        });
        nds.erase(unique(nds.begin(),nds.end()),nds.end());
        for(int j = 1;j < nds.size();j++){
            int lc = lca(nds[j],nds[j - 1]);
            bian1[lc].push_back(nds[j]);
        }
        dfs2(nds[0]);
        for(int j = 0;j < nds.size();j++){
            ps[i].push_back(make_pair(cnt[nds[j]],nds[j]));
        }
        for(int v: nds){
            cnt[v] = 0;
            bian1[v].clear();
        }
        sort(ps[i].begin(),ps[i].end(),greater<pair<int,int>>());
        for(int p : que[i]){
            que1[qr[p]].push_back(p);
        }
    }
    //assert(0);
    bo.init(tot);
    for(int i = 1;i <= n;i++){
        bo.update(dfn[ep[i]],dfn[ep[i]] + siz[ep[i]] - 1,i);
        for(int p : que1[i]){
            for(pair<int,int> ch : ps[qk[p]]){
                if(bo.query(dfn[ch.second]) >= ql[p]){
                    ans[p] = ch.first;
                    break;
                }
            }
        }
    }
    for(int i = 1;i<=m;i++){
        cout<<ans[i]<<'\n';
    }
}
/*
N^2/B(N) + MlogN + MB
*/